/**
 * 给定一个矩阵，求左上到右下乘积最大的路径，求乘积
 * 因为有正有负，必须同时维持最大值与最小值
 * 更新时，必须区分当前格的正负，分情况讨论
 * 
 */
class Solution {

using llt = long long;
using vi = vector<int>;
using vll = vector<llt>;
enum {None = 0x1F2F3F4F5F6F7F8F};

vector<vll> Dax, Din;
int N;
int M;

public:
    int maxProductPath(vector<vector<int>>& grid) {
        N = grid.size();
        M = grid[0].size();
        Dax.assign(N, vll(M, None));
        Din.assign(N, vll(M, None));

        Dax[0][0] = Din[0][0] = grid[0][0];
        for(int i=0;i<N;++i)for(int j=0;j<M;++j){
            if(0 == i and 0 == j) continue;

            auto v = grid[i][j];
            if(i > 0){
                if(v >= 0){
                    chkmax(Dax[i][j], Dax[i - 1][j] * v);
                    chkmin(Din[i][j], Din[i - 1][j] * v);
                }else{
                    chkmax(Dax[i][j], Din[i - 1][j] * v);
                    chkmin(Din[i][j], Dax[i - 1][j] * v);
                }
            }
            if(j > 0){
                if(v >= 0){
                    chkmax(Dax[i][j], Dax[i][j - 1] * v);
                    chkmin(Din[i][j], Din[i][j - 1] * v);
                }else{
                    chkmax(Dax[i][j], Din[i][j - 1] * v);
                    chkmin(Din[i][j], Dax[i][j - 1] * v);
                }
            }
        }
        if(Dax[N - 1][M - 1] < 0) return -1;
        return Dax[N - 1][M - 1] % (1000000000 + 7);
    }
    
    void chkmin(llt & d, llt a){
        if(a == None) return;
        if(d == None or a < d) d = a;
    }

    void chkmax(llt & d, llt a){
        if(a == None) return;
        if(d == None or d < a) d = a;
    }
};
